package top.datacluster.basic.sort;

public class HeapSort {

    private int[] data;

    private int size;

    public HeapSort(int[] src){
        data = new int[src.length + 1];
        int index = 1;
        data[index++] = src[0];
        while (index < data.length){
            data[index] = src[index - 1];
            int i = index;
            while (i > 1){
                if (data[i] > data[i / 2]){
                    exch(i, i / 2);
                }
                i = i / 2;
            }
            index++;
        }
    }


    public void sort(){
        int lenght = data.length - 1;
        while (lenght > 0){
            System.out.println(data[1]);
            data[1] = data[lenght];
            lenght--;
            int i = 1;
            while (i < lenght){
                int child = i * 2;
                if (data[i * 2] < data[i * 2 + 1]){
                    child ++;
                }
                if (data[i] < data[child]){
                    exch(i, child);
                }else{
                    break;
                }

            }
        }
    }

    private void exch(int j, int k){
        int temp = data[j];
        data[j] = data[k];
        data[k] = temp;
    }

    public void print(){
        for (int i : data){
            System.out.print(i + " ");

        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] test = new int[]{4, 1, 2, 6, 9};
        HeapSort heapSort = new HeapSort(test);
        heapSort.print();
        heapSort.sort();
    }
}
